Skip to main content

3-28 1014. 最佳观光组合

Date：2022-03-27 22:00:39

题目：1014. 最佳观光组合 ( 中等😕 )​

给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。

一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。

返回一对观光景点能取得的最高分。

示例​

示例 1：

输入：values = [8,1,5,2,6]
输出：11
解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

示例 2：

输入：values = [1,2]
输出：2

分析​

  • 暴力枚举

    O(n^2), O(1)

  • 脑筋急转弯

    将 values[i] + values[j] + i - j 转化为 values[i] + i + values[j] - j，咋一眼看不出来有什么用。

    认真看第 0 位的 8+0，第 2 位的 5-2，第 3 位的 2-3，第 4 位的 6-4

    它们的组合，第 0 位和第 2 位组合起来是最大的 8+0+5-2 = 11

    image-20220328220614266

题解​

脑筋急转弯

function maxScoreSightseeingPair(values: number[]): number {
  const len = values.length
  let ans = 0,
    mx = 0
  for (let i = 0; i < len; ++i) {
    // value[i] + i + values[j] - j
    ans = Math.max(ans, mx + values[i] - i)

    mx = Math.max(mx, values[i] + i)
  }

  return ans
}

使用

function main() {
  // const values = [8, 1, 5, 2, 6]
  const values = [1, 2]

  console.log('[]:', maxScoreSightseeingPair(values))
}

main()

export {}